class Solution
{
public:
    int countGoodNumbers(long long n)
    {
        long long evenIdCount = (n + 1) / 2;
        long long oddIdCount = n - evenIdCount;
        long long result = 1;

        long long pow5 = 5;
        long long pow4 = 4;
        constexpr long long MOD = 1000000007LL;

        // 5 ^ even * 4 ^ odd
        while (evenIdCount)
        {
            if (evenIdCount & 1)
            {
                result *= pow5;
                result %= MOD;
            }
            pow5 *= pow5;
            pow5 %= MOD;
            evenIdCount = evenIdCount >> 1;
        }

        while (oddIdCount)
        {
            if (oddIdCount & 1)
            {
                result *= pow4;
                result %= MOD;
            }
            pow4 *= pow4;
            pow4 %= MOD;
            oddIdCount = oddIdCount >> 1;
        }

        return result;
    }
};